Search for: All records

We study the problem of jointly pricing and designing a smart transit system, where a transit agency (the platform) controls a fleet of demand-responsive vehicles (cars) and a fixed line service (buses). The platform offers commuters a menu of options (modes) to travel between origin and destination (e.g., direct car trip, a bus ride, or a combination of the two), and commuters make a utility-maximizing choice within this menu, given the price of each mode. The goal of the platform is to determine an optimal set of modes to display to commuters, prices for these modes, and the design of the transit network in order to maximize the social welfare of the system. In this work, we tackle the commuter choice aspect of this problem, traditionally approached via computationally intensive bilevel programming techniques. In particular, we develop a framework that efficiently decouples the pricing and network design problem: Given an efficient (approximation) algorithm for centralized network design without prices, there exists an efficient (approximation) algorithm for decentralized network design with prices and commuter choice. We demonstrate the practicality of our framework via extensive numerical experiments on a real-world data set. We moreover explore the dependence of metrics such as welfare, revenue, and mode usage on (i) transfer costs and (ii) cost of contracting with on-demand service providers and exhibit the welfare gains of a fully integrated mobility system. Funding: This work was supported by the National Science Foundation [Awards CMMI-2308750, CNS-1952011, and CMMI-2144127]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0452 . 

This paper describes a newly launched project that will produce a new approach to public microtransit for underserved communities. Public microtransit cannot rely on pricing signals to manage demand, and current approaches face the challenges of simultaneously being underutilized and overextended. This project conceives of the setting as a sociotechnical system. Its main idea is to engage users through AI agents in conjunction with platform constraints to find solutions that purely technical conceptions cannot find. The project was specified over an intense series of discussions with key stakeholders (riders, city government, and nongovernmental agencies) and brings together expertise in the disciplines of AI, Operations Research, Urban Planning, Psychology, and Community Development. The project will culminate in a pilot study, results from which will facilitate the transfer of its technology to additional communities. 

The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times. 

The rise of on-demand mobility technologies over the past decade has sparked interest in the integration of traditional transit and on-demand systems. One of the main reasons behind this is the potential to address a fundamental trade-off in transit: the ridership versus coverage dilemma. However, unlike purely fixed systems or purely on-demand systems, integrated systems are not well understood; their planning and operational problems are significantly more challenging, and their broader implications are the source of a heated debate. Motivated by this debate, we introduce the dynamicity gap, a general concept that quantifies the attainable benefit of allowing (but not requiring) dynamic components in the response strategy to a multistage optimization problem. Although computing the dynamicity gap exactly may be intractable, we develop an analytical framework with which to approximate it as a function of problem input parameters. The framework allows us to certify the value of dynamism (i.e., a dynamicity gap greater than one) for certain combinations of problem input parameters. We showcase our approach with two sets of computational experiments, from which we gain both qualitative and quantitative insights about the settings in which the integration of transit and on-demand systems may certifiably be a worthwhile investment. Funding: This work was partially supported by the National Science Foundation [Grants DMS-1839346 and CNS-1952011]. Part of this research was performed while the authors were visiting the Institute for Pure and Applied Mathematics, which is supported by the National Science Foundation [Grant DMS-1925919]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1193 . 

This work considers the sensitivity of commute travel times in US metro areas due to potential changes in commute patterns, for example caused by events such as pandemics. Permanent shifts away from transit and carpooling can add vehicles to congested road networks, increasing travel times. Growth in the number of workers who avoid commuting and work from home instead can offset travel time increases. To estimate these potential impacts, 6-9 years of American Community Survey commute data for 118 metropolitan statistical areas are investigated. For 74 of the metro areas, the average commute travel time is shown to be explainable using only the number of passenger vehicles used for commuting. A universal Bureau of Public Roads model characterizes the sensitivity of each metro area with respect to additional vehicles. The resulting models are then used to determine the change in average travel time for each metro area in scenarios when 25% or 50% of transit and carpool users switch to single occupancy vehicles. Under a 25% mode shift, areas such as San Francisco and New York that are already congested and have high transit ridership may experience round trip travel time increases of 12 minutes (New York) to 20 minutes (San Francisco), costing individual commuters $1065 and $1601 annually in lost time. The travel time increases and corresponding costs can be avoided with an increase in working from home. The main contribution of this work is to provide a model to quantify the potential increase in commute travel times under various behavior changes, that can aid policy making for more efficient commuting. 

We construct an agent-based SEIR model to simulate COVID-19 spread at a 16000-student mostly non-residential urban university during the Fall 2021 Semester. We find that mRNA vaccine coverage at 100% combined with weekly screening testing of 25% of the campus population make it possible to safely reopen to in-person instruction. Our simulations exhibit a right-skew for total infections over the semester that becomes more pronounced with less vaccine coverage, less vaccine effectiveness and no additional preventative measures. This suggests that high levels of infection are not exceedingly rare with campus social connections the main transmission route. Finally, we find that if vaccine coverage is 100% and vaccine effectiveness is above 80%, then a safe reopening is possible even without facemask use. This models possible future scenarios with high coverage of additional “booster” doses of COVID-19 vaccines. 

Many transit agencies operating paratransit and microtransit ser-vices have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to signifi-cant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse-our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.